package zfc;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class P1 {
    public int solve(String seq, int[][] rules) {
        // 获取最大长度
        List<Integer> dp = new ArrayList<>();
        dp.add(0);

        //
        Arrays.sort(rules, (a, b) -> {
            return a[0] - b[0];
        });
        // base
        for (int i = 0; i < rules.length; i++) {
            int[] rule = rules[i];
            while (dp.size() < rule[0]) {
                dp.add(dp.get(dp.size() - 1));
            }
            //
            int max = rule[1];
            for (int j = 0; j < i; j++) {
                int[] rule2 = rules[j];
                if (rule[0] - rule2[0] >= 1) {
                    max = Math.max(max, dp.get(rule[0] - rule2[0]) + rule2[1]);
                }
            }
            dp.add(max);
        }
        int total = 0;
        label:
        for (int i = 0; i < seq.length(); i++) {
            //跳过零
            while (seq.charAt(i) == '0') {
                continue label;
            }
            //收集一
            int len = 0;
            while (i < seq.length() && seq.charAt(i) == '1') {
                len++;
                i++;
            }
            i -= 1;
            //计算结果发
            if (dp.size() <= len) {
                for (int j = dp.size(); j <= len; j++) {//计算结果
                    int max = dp.get(j - 1);
                    for (int[] rule : rules) {
                        if (j - rule[0] >= 1) {
                            int tmp = rule[1] + dp.get(j - rule[0]);
                            max = Math.max(max, tmp);
                        }
                    }
                    dp.add(max);
                }
            }
            total += dp.get(len);
        }
        return total;
    }

    public static void main(String[] args) {
        String seq = "111111011111";
        int[][] rules = new int[][]{{3, 10}, {4, 15}};
        System.out.println(new P1().solve(seq, rules));
    }
}
